//
//  Problem1850.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/11.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1850. 邻位交换的最小次数
 给你一个表示大整数的字符串 num ，和一个整数 k 。
 如果某个整数是 num 中各位数字的一个 排列 且它的 值大于 num ，则称这个整数为 妙数 。可能存在很多妙数，但是只需要关注 值最小 的那些。

 例如，num = "5489355142" ：
     第 1 个最小妙数是 "5489355214"
     第 2 个最小妙数是 "5489355241"
     第 3 个最小妙数是 "5489355412"
     第 4 个最小妙数是 "5489355421"
 返回要得到第 k 个 最小妙数 需要对 num 执行的 相邻位数字交换的最小次数 。
 测试用例是按存在第 k 个最小妙数而生成的。

 示例 1：
     输入：num = "5489355142", k = 4
     输出：2
     解释：第 4 个最小妙数是 "5489355421" ，要想得到这个数字：
     - 交换下标 7 和下标 8 对应的位："5489355142" -> "5489355412"
     - 交换下标 8 和下标 9 对应的位："5489355412" -> "5489355421"
 示例 2：
     输入：num = "11112", k = 4
     输出：4
     解释：第 4 个最小妙数是 "21111" ，要想得到这个数字：
     - 交换下标 3 和下标 4 对应的位："11112" -> "11121"
     - 交换下标 2 和下标 3 对应的位："11121" -> "11211"
     - 交换下标 1 和下标 2 对应的位："11211" -> "12111"
     - 交换下标 0 和下标 1 对应的位："12111" -> "21111"
 示例 3：
     输入：num = "00123", k = 1
     输出：1
     解释：第 1 个最小妙数是 "00132" ，要想得到这个数字：
     - 交换下标 3 和下标 4 对应的位："00123" -> "00132"
 提示：
     2 <= num.length <= 1000
     1 <= k <= 1000
     num 仅由数字组成
 */
@objcMembers class Problem1850: NSObject {
    func solution() {
        print(getMinSwaps("5489355142", 4))
        print(getMinSwaps("11112", 4))
        print(getMinSwaps("00123", 1))
    }
    
    /*
     1:
     */
    func getMinSwaps(_ num: String, _ k: Int) -> Int {
        var charts = Array(num)
        
        // 1: 反转k次
        var i = 0
        while i < k {
            getNextMaxNum(&charts)
            i += 1
        }
        
        var result = 0
        // 2: 对比2个数组
        var lcharts = Array(num)
        i = 0
        while i < charts.count {
            // 1: 找到第一个不想等的字符位置
            if charts[i] == lcharts[i] {
                i += 1
                continue
            }
            
            // 2: 找到这个字符，在原字符串中的位置
            var j = i + 1
            while charts[i] != lcharts[j] {
                j += 1
            }
            
            // 3: 将这个字符，移动到新的位置
            var k = j
            while k > i {
                let temp = lcharts[k]
                lcharts[k] = lcharts[k-1]
                lcharts[k-1] = temp
                k -= 1
                
                result += 1
            }
        }
        
        return result
    }
    
    func getNextMaxNum(_ charts: inout [Character]) {
        // 1: 找到第一个 比较小
        var i = charts.count - 2
        while i >= 0, charts[i] >= charts[i+1] {
            i -= 1
        }
        // 2: 找到第一个比上面的i大于的位置，因为后面的是递增的
        // 1 2 3 100 98 97 96
        // 1 2 100 101 98 97 96
        var j = charts.count - 1
        while j >= 0, charts[i] >= charts[j] {
            j -= 1
        }
        // 3: 交换这2个位置
        var temp = charts[j]
        charts[j] = charts[i]
        charts[i] = temp
        
        // 4: 这时i后面的是一个递增的，然后将这个转换成递减
        i = i + 1
        j = charts.count - 1
        while i < j {
            temp = charts[j]
            charts[j] = charts[i]
            charts[i] = temp
            
            i += 1
            j -= 1
        }
    }
}
